package com.whitedust;

import java.util.*;

public class CreateTree {
    // 节点定义
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) {
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    //以下是具体实现代码，用中序遍历来举例
    static void recrution(TreeNode root,List<Integer> result){
        //前序中左右 中序左中右 后序左右中 
        if(root==null)
            return;
        recrution(root.left,result);
        result.add(root.val);
        recrution(root.right,result);
    }
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        recrution(root,result);
        return result;
    }

    //输入数组并创建二叉树调用方法后输出结果
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        if(n==0)
        {
            System.out.println(" ");
            return;
        }
        int[] node=new int[n];
        for(int i=0;i<n;i++)
            while(sc.hasNextInt()){
                node[i]=sc.nextInt();
            }
        TreeNode root=createTree(node);
        // 获取中序遍历结果
        List<Integer> res = inorderTraversal(root);
        // 输出中序遍历结果
        for (int i = 0; i < res.size(); i++) {
            System.out.print(res.get(i));
            System.out.print(" ");
        }
    }

    public static TreeNode createTree(int[] arr){
        List<TreeNode> list=new ArrayList<>();
        //先把node数组的值填充到list里面
        int n = arr.length;
        TreeNode root = new TreeNode();//root需要在外面定义才能保证作用域
        for(int i = 0;i < n;i++){
            TreeNode node = new TreeNode();
            if(arr[i] != -1){
                node.val=arr[i];
            }
            list.add(node);
            if(i == 0)
                root =node;
        }
        //为每个节点添加左右子树
        for(int i = 0;i * 2 + 1 < n;i++){
            TreeNode node = list.get(i);
            if(node != null){
                node.left = list.get(i * 2 + 1);
                if(i * 2 + 2 < n){
                    node.right = list.get(i * 2 + 2);
                }
            }
        }
        return root;
    }
}